package com.yc.leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * 动态规划
 */
public class DyncmicPrograming {
    public static void main(String[] args) {
        DyncmicPrograming dp = new DyncmicPrograming();
//        dp.calculateMinimumHP();
        dp.minPathSum();
    }

    /**
     * 恶魔们抓住了公主并将她关在了地下城 dungeon 的 右下角 。地下城是由 m x n 个房间组成的二维网格。我们英勇的骑士最初被安置在 左上角 的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。
     * 骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。
     * 有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数，则表示骑士将损失健康点数）；其他房间要么是空的（房间里的值为 0），要么包含增加骑士健康点数的魔法球（若房间里的值为正整数，则表示骑士将增加健康点数）。
     * 为了尽快解救公主，骑士决定每次只 向右 或 向下 移动一步。
     * 返回确保骑士能够拯救到公主所需的最低初始健康点数。
     *
     * 注意：任何房间都可能对骑士的健康点数造成威胁，也可能增加骑士的健康点数，包括骑士进入的左上角房间以及公主被监禁的右下角房间。
     */
    public void calculateMinimumHP() {
        int[][] s = {{-2,-3,3},{-5,-10,1},{10,30,-5}};
        System.out.println(calculateMinimumHP_1(s));
    }

    public int calculateMinimumHP_1(int[][] dungeon) {
        int r = dungeon.length;
        int c = dungeon[0].length;
        int[][] minDir = new int[r][c];//"距离右下角最短距离"（最大的值）

        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                minDir[r][c] = Integer.MIN_VALUE;//因为要找最大值，所以先把所有点初始化为最小值
            }
        }
        //把右下角的值初始化为所有节点的初始值
        minDir[r-1][c-1] = dungeon[r-1][c-1];

        for (int i = r-1; i >= 0; i--) {//外数组（第一个中括号）
            for (int j = c-1; j >= 0; j--) {//内数组（第二个中括号）

                //上面
                int up = minDir[i][j] + dungeon[i][j-1];
                if (minDir[i][j-1] < up) {
                    minDir[i][j-1] = up;
                }

                //左边

                int left = minDir[i][j] + dungeon[i-1][j];
                if (minDir[i-1][j] < left) {
                    minDir[i-1][j] = left;
                }

            }
        }

        return minDir[0][0];
    }

    /**
     * 给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
     *
     * 说明：每次只能向下或者向右移动一步。
     */
    public void minPathSum() {
//        int[][] s = {{1,3,1},{1,5,1},{4,2,1}};
        int[][] s = {{1,2,3},{4,5,6}};
        System.out.println(minPathSum_1(s));
    }

    public int minPathSum_1(int[][] grid) {
        int r = grid.length;
        int c = grid[0].length;
        int[][] minDir = new int[r][c];//"距离右下角最短距离"（最大的值）

        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                minDir[i][j] = Integer.MAX_VALUE;//因为要找最小值，所以先把所有点初始化为最大值
            }
        }
        //把左上角初始化为他自己
        minDir[0][0] = grid[0][0];

        for (int i = 0; i < r; i++) {//外数组（第一个中括号）
            for (int j = 0; j < c; j++) {//内数组（第二个中括号）

                //下面
                if (i+1 < r) {
                    int down = minDir[i][j] + grid[i+1][j];
                    if (down < minDir[i+1][j]) {
                        minDir[i+1][j] = down;
                    }
                }


                //右边
                if (j+1 < c) {
                    int right = minDir[i][j] + grid[i][j+1];
                    if (right < minDir[i][j+1]) {
                        minDir[i][j+1] = right;
                    }
                }

            }
        }

        return minDir[r-1][c-1];
    }

    public int longestPalindrome(String s) {
        if (s.length() < 2) {
            return s.length();
        }

        Map<Character, Integer> map = new HashMap<>();
        for (int i=0; i<s.length(); i++) {
            Integer num = map.get(s.charAt(i));
            if (num == null) {
                map.put(s.charAt(i), 1);
            } else {
                map.put(s.charAt(i), ++num);
            }
        }

        int max = 0;
        boolean haveMid = false;//是否一斤有中间
        for (Character key : map.keySet()) {
            int num = map.get(key);
            if (num%2==1) {
                if (!haveMid) {
                    haveMid = true;
                    max += num;
                } else {
                    max += (num/2)*2;
                }
            } else {
                max += num;
            }
        }

        return max;

    }

}
